Data packet loss is a common phenomenon in lossy network communications such as wireless network communications. For example, noise and/or interference can change or erase parts of a transmitted data packet. The corrupted data packets may be detected and considered as lost packets. Several techniques have been devised to recover from corrupted data packets including forward error correction and linear network coding. For many practical applications, it has been found that linear network coding has a throughput gain over forwarding in unicast and multicast networks.
The capacity of networks with packet loss for many scenarios can be achieved by using random linear network coding (RLNC). In a typical RLNC scheme, a source node transmits random linear combinations of the input packets, one or more intermediate nodes transmits random linear combinations of the packets it has received, and a destination node can decode the input packets once it has received enough coded packets with linear independent coding vectors. Erasure code is not required for each link as the network code itself can play the role of an end-to-end erasure code.
However, there are several problems to be considered when implementing RLNC schemes in practice. For example, computational costs of encoding and decoding, storage and computational costs at intermediate nodes, and overhead for coefficient vectors, to name a few. Conventional attempts to address these problems are ineffective, inefficient and/or suboptimal.